# coding=utf-8

"""
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?
"""

"""
1   如果允许使用额外的空间：
    可以将所有 node 的地址缓存到一个大的 hash 中
    如果存在重复的 node 标识则证明一定存在环

t = O(1)
space = O(n)

2   如果不允许使用额外的空间
    可以使用不同的步长遍历 list 看是不是重合
    如何证明？

    因为如果存在环 遍历就不可能结束 会一直进行下去
    而且 步长大的将会率先进入循环

    1 ----> 2
     ^     /
      \  V
       3

    这个步长为 1，2 对应的序列分别为

    1 2 3 1 2 3 ...
    1 3 2 2 2 2 ...

    通过数学归纳法是可以证明的
    当假设 n 成立的时候 n + 1 在 n 之后，因此是必然成立的

    loop = 1 的时候
    F = 1
    S = 1
    成立

    假设 len = n 的时候 存在 loop = m 时满足 F = S
    => len = n + 1 的时候 存在同样的 loop = m 满足命题
"""


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def const_list_from_array(array):
    l = None

    for item in array:
        if l is None:
            l = ListNode(item)
            l.next = None
            _l = l

        else:
            l.next = ListNode(item)
            l = l.next

    return _l


def print_list(l1):
    list_str = ""

    while l1:
        list_str = "[%s] ->" % l1.val
        print list_str,
        l1 = l1.next

    print "None",


class Solution(object):

    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool

        遍历 list 保存元素到 hash 中
        t = O(n)
        s = O(n)

        竟然会超时。。
        再提交竟然又 ac 了。。
        """

        l = head
        ids = []
        while l is not None:
            if id(l) in ids:
                return True

            ids.append(id(l))
            l = l.next

        return False

    def hasCycle2(self, head):
        """
        :type head: ListNode
        :rtype: bool

        使用快慢指针
        """

        fast = head
        slow = head

        if head is None or head.next is None:
            return False

        slow = slow.next
        fast = fast.next.next

        while fast is not None and slow is not None:
            slow = slow.next

            if fast.next is None:
                return False

            fast = fast.next.next

            if fast is None:
                return False

            if fast.val == slow.val:
                return True

        return False


if __name__ == "__main__":
    solution = Solution()

    l1 = ListNode(9)
    _l1 = l1
    l1.next = ListNode(3)
    l1 = l1.next
    l1.next = _l1

    # test_list = const_list_from_array(_l1)
    print solution.hasCycle2(_l1)
